﻿/*
素数的排位 
Time Limit:200MS  Memory Limit:32768K


Description:
聪聪在研究素数，可是为搞清一些素数究竟在素数集合中排名老几，伤透了脑筋。
还是你帮他编个程序搞定吧，否则，他慢腾腾慢腾腾地数，数到什么时候去?!

Input:
输入有正整数N（1≤N≤1000000）若干。 
Output:
运行结果每个数占1行，结果中的每个数是输入的正整数在素数集合中的排位。
如果输入的不是素数（这太有可能了）那就输出一个0表示。 
Sample Input:
2
6
4
5
13
Sample Output:
1
0
0
3
6
*/	
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <cstdlib>
using namespace std;
enum{DELETED=0, KEPT=1};

int main()
{
	vector<unsigned> nums;
	for (unsigned num;cin >> num; nums.push_back(num))
		;
	unsigned max_num = *max_element(nums.begin(), nums.end());
	
	vector<unsigned> primes(max_num/2+1, KEPT);	//记录从2n+3的质数置位
	
	unsigned counter=1;
	for (unsigned i=1, p=i+i+1; p*p<=max_num; ++i)
		if(primes[i])
		{		
			p=i+i+1;
			++counter;
			for (unsigned j=i, q=j+j+1; q*q<=max_num; ++j)
				if(primes[j])
				{
					q=j+j+1;
					++counter;
					for (unsigned r=p*q; r<=max_num; r*=p)
						primes[(r-1)>>1]=DELETED;
				}
		}
	{
		for (unsigned k=1, i=1; i<=counter;++k)
			if(primes[k])
			{
				++i;
				primes[k]=i;
				
			}
	}

	for (vector<unsigned>::iterator it=nums.begin(); it!=nums.end();++it)
	{
		if(1==*it)
			cout<<0<<endl;
		else if(2==*it)
			cout<<1<<endl;
		else{
			unsigned num=*it-1;
			if(0==num%2)
				cout<<primes[num/2]<<endl;
			else
				cout<<0<<endl;
		}
		
	}
		
		return EXIT_SUCCESS;
}
/*
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <cstdlib>
using namespace std;
enum{DELETED=0, KEPT=1};

int main()
{
	vector<unsigned> nums;
	for (unsigned num;cin >> num; nums.push_back(num))
		;
	unsigned max_num = *max_element(nums.begin(), nums.end());
	
	max_num/=2;
	vector<unsigned> primes(max_num+32, KEPT);	//记录从2n+3的质数置位
	
	unsigned counter=1;
	for (unsigned i=0; i<=max_num; ++i)
		if(primes[i])
		{
			++counter;
			primes[i]=counter;
			unsigned prime=i+i+3;			
			//cout<<prime<<": "<<primes[i]<<endl;
			for (unsigned k=prime+i; k<=max_num; k+=prime)
				primes[k]=DELETED;
		}

	for (vector<unsigned>::iterator it=nums.begin(); it!=nums.end();++it)
	{
		if(1==*it)
			cout<<0<<endl;
		else if(2==*it)
			cout<<1<<endl;
		else{
			unsigned num=*it-3;
			if(0==num%2)
				cout<<primes[num/2]<<endl;
			else
				cout<<0<<endl;
		}


	}
	
	return EXIT_SUCCESS;
}
*/
/*
#include<stdio.h>

int a[1000005];
int p[1000005]={0};
void main()
{
        int n,i,j,s=1;
        for(i=2;i<500001;i++)   //筛掉2的倍数
          a[2*i]=1;
        for(i=3;i<1000;i+=2)  //筛掉3,5,7....的倍数
          if(!a[i]) for(j=i*i;j<1000001;j+=(i<<1)) a[j]=1;
        for(i=2;i<1000001;i++)
          if(!a[i]) p[i]=s++;
        while (scanf("%d",&n)!=EOF)
          printf("%d\n",p[n]);
}

#include<stdio.h>
int a[1000001]={0};
int main()
{
        int n,count=2,i,j;
        a[1]=1;
        for(i=2;i<=500000;i++)
                a[i*2]=1;
        for(i=3;i<=1000;i+=2)
                if(a[i]==0)
                        for(j=i;j<=1000000/i;j+=2)
                                a[j*i]=1;
        for(i=3;i<=1000000;i+=2)
                if(!a[i])
                        a[i]=count++;
        while(scanf("%d",&n)!=EOF)
        {
                if(n!=2)
                        if(a[n]==1)
                                printf("%d\n",a[n]-1);
                        else
                                printf("%d\n",a[n]);
                else
                        printf("1\n");
        }
        return 0;
}
*/
/*
int main()
{
	vector<unsigned> nums;
	for (unsigned num;cin >> num; nums.push_back(num))
		;
	unsigned max_num = *max_element(nums.begin(), nums.end());

	//	unsigned max_num=9;

	vector<unsigned> primes;
	primes.push_back(2);
	primes.push_back(3);
	primes.push_back(5);

	unsigned prime = 5;
	int gap = 2;

	while (true)
	{
		prime += gap;
		if (prime > max_num)
			break;
		gap = 6 - gap;
		bool is_prime = true;

		for (vector<unsigned>::size_type i = 0, size = primes.size();
			is_prime && primes[i] * primes[i] <= prime;
			i++)
			if (0 == prime % primes[i])
			{
				is_prime = false;
			}

		if (is_prime)
			primes.push_back(prime);
	}

	for (vector<unsigned>::iterator it=nums.begin(); it!=nums.end(); ++it)
	{
		vector<unsigned>::iterator pos=lower_bound(primes.begin(), primes.end(), *it);
		if(*pos==*it)
			cout<< (1+distance(primes.begin(), pos))<<endl;
		else
			cout<<0<<endl;
	}
//	copy(primes.begin(), primes.end(), ostream_iterator<unsigned>(cout, " "));
	return 0;
}
*/